package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: parentheseValid
 * @author: chanzhugang
 * @create: 2022/06/08 15:39
 */
public class ParentheseValid2 {

    public static void main(String[] args) {
        ParentheseValid2 parentheseValid2 = new ParentheseValid2();
        String s = "({}[])";
        boolean res = parentheseValid2.isValid(s);
        System.out.println(res);
    }

    /**
     * 20. 有效的括号
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        /**
         * 左括号压入栈， 右括号和栈顶元素比较是否相等
         */
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    // 没有压入右括号
                    return false;
                }
                Character popVal = stack.pop();
                if (c == ')' && popVal != '(') {
                    return false;
                }
                if (c == ']' && popVal != '[') {
                    return false;
                }
                if (c == '}' && popVal != '{') {
                    return false;
                }
            }
        }
        // 栈是否为空，空表示括号消完了
        return stack.isEmpty();
    }
}